package com.bwt.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class ShellSort {
	public static void main(String[] args) {
	/*	int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
		shellSort(arr);
		System.out.println(Arrays.toString(arr));*/
		/*[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]*/

		int[] arr = new int[80000];
		for(int i = 0;i < 80000;i++){
			arr[i] = (int)(Math.random() * 80000);	//自动生成[0,80000)之间的随机数
		}

		//排序前的时间:
		Date data = new Date();
		SimpleDateFormat simt = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String dateS = simt.format(data);
		System.out.println("排序前的时间是:" + dateS);

		shellSort2(arr);

		//System.out.println(Arrays.toString(arr));
		//排序后的时间:
		Date data2 = new Date();
		SimpleDateFormat simt2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String dateS2 = simt2.format(data2);
		System.out.println("排序后的时间是:" + dateS2);
		//交换法
		//排序前的时间是:2022-07-11 15:01:58
		//排序后的时间是:2022-07-11 15:02:13

		//移位法
		//排序前的时间是:2022-07-11 15:25:59
		//排序后的时间是:2022-07-11 15:25:59
	}

	//希尔排序移位法
	public static void shellSort2(int[] arr) {
		for (int gap = arr.length; gap>0; gap /= 2) {  //5, 2,1
			//从第gap个元素, 逐个对其所在的组进行插入排序
			for (int i = gap; i < arr.length; i++) {
				int j = i;
				int temp = arr[j];
				if (arr[j]< arr[j - gap]) {
					while (j - gap >= 0 && temp < arr[j - gap]) {
						//移动
						arr[j] = arr[j - gap];
						j -= gap;
					}
					// 当退出while 循环后 temp 就找到了插入的位置
					arr[j] = temp;
				}
			}
		}
	}

	//shell 排序交换法
	public static void shellSort(int[] arr) {
		int temp = 0;
		for (int gap = arr.length; gap>0; gap /= 2) {
			for (int i = gap; i < arr.length; i++) {
				//遍历各组中所有的元素(共5组, 每组有两个元素)
				for (int j = i - gap; j >= 0; j -= gap) {
					//如果当前这个元素 大于 加上步长后的元素
					if (arr[j + gap] < arr[j]) {
						temp = arr[j];
						arr[j] = arr[j + gap];
						arr[j + gap] = temp;
					}
				}
			}
		}
		/*//希尔排序过程推到
		//第一轮 排序  是将10个数据分成了5组
		int temp = 0;
		for (int i = 5; i < arr.length; i++) {
			//遍历各组中所有的元素(共5组, 每组有两个元素)
			for (int j = i - 5; j >= 0; j -= 5) {
				//如果当前这个元素 大于 加上步长后的元素
				if (arr[j + 5] < arr[j]) {
					temp = arr[j];
					arr[j] = arr[j + 5];
					arr[j + 5] = temp;
				}
			}
		}

		System.out.println("第一轮后排序情况:" + Arrays.toString(arr));

		temp = 0;
		for (int i = 2; i < arr.length; i++) {
			//遍历各组中所有的元素(共5组, 每组有两个元素)
			for (int j = i - 2; j >= 0; j -= 2) {
				//如果当前这个元素 大于 加上步长后的元素
				if (arr[j + 2] < arr[j]) {
					temp = arr[j];
					arr[j] = arr[j + 2];
					arr[j + 2] = temp;
				}
			}
		}

		System.out.println("第二轮后排序情况:" + Arrays.toString(arr));

		temp = 0;
		for (int i = 1; i < arr.length; i++) {
			//遍历各组中所有的元素(共5组, 每组有两个元素)
			for (int j = i - 1; j >= 0; j -= 1) {
				//如果当前这个元素 大于 加上步长后的元素
				if (arr[j + 1] < arr[j]) {
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}

		System.out.println("第二轮后排序情况:" + Arrays.toString(arr));

		*//*第一轮后排序情况:[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
第二轮后排序情况:[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
第二轮后排序情况:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]*/
	}
}
